/*
 * @lc app=leetcode.cn id=152 lang=cpp
 *
 * [152] 乘积最大子数组
 */

// @lc code=start
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        //[2,3,-2,4,-1]
        //动态规划，存储一个当前最大和当前最小
        //cur_max = max(cur_max * nums[i], cur_min * nums[i], nums[i])
        //cur_min = min(cur_max * nums[i], cur_min * nums[i], nums[i])
        // 2 6 -2   4   48   
        // 2 3 -12 -48  -4

        if(nums.size() == 0) return 0;

        int cur_max = nums[0], cur_min = nums[0];
        int ans = nums[0];
        for(int i = 1; i < nums.size(); i++){
            int t1 = cur_max * nums[i];
            int t2 = cur_min * nums[i];
            cur_max = max(t1, max(nums[i], t2));
            cur_min = min(t1, min(nums[i], t2));
            ans = max(ans, cur_max);
        }
        return ans;
    }
};
// @lc code=end

